package greedyMind

import "sort"

//给孩子分配糖果问题
// 有m个糖果，大小分别是s1, s2 ,s3,s4
// 有n个孩子，每个孩子对糖果的期望大小是g1 ,g2, g3, g4, g5
// 条件是糖果少，孩子多 m<n 如何分配才能尽可能满足最多数量的孩子

func CandyAllocation(candys, wishs []int) []int {
	sort.Ints(candys)
	sort.Ints(wishs)

	var result []int
	// 从需求最小的孩子开始分配糖果，找出能满足孩子的最小糖果分配给他
	si, gi := 0, 0
	candyAllocation(si, gi, candys, wishs, &result)
	return result
}

// si表示剩余糖果起始大小
// gi表示孩子对糖果期望起始大小
func candyAllocation(si, gi int, candys, wishs []int, result *[]int) {
	if si > len(candys)-1 {
		return
	}
	if gi > len(wishs)-1 {
		return
	}
	isContinue := false
	for i := si; i <= len(candys)-1; i++ {
		// 找到满足孩子希望的最小糖果
		if wishs[gi] <= candys[i] {
			*result = append(*result, candys[i])
			si = i + 1
			gi++
			isContinue = true
			break
		} else {
			// 如果当前糖果只剩最后一个，但是不满足分配方案
			if i == len(candys)-1 {
				isContinue = false
				break
			}
		}
	}
	if isContinue {
		candyAllocation(si, gi, candys, wishs, result)
	}
}
